
%% bare_conf.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE conference paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE!
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex
%%*************************************************************************

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/



% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
\documentclass[10pt, conference, a4paper, compsocconf]{IEEEtran}
% customized to Vietnamese codes and free-modifying header/footer by Nguyễn Trường Thắng
\usepackage{amsmath,amsxtra,amssymb,amsthm,latexsym,amscd,amsfonts}
\usepackage[utf8]{vietnam}
\usepackage{float}
\usepackage{algorithm}
\usepackage{algpseudocode}
%% We will completely define our own header strings, so switch the fancy
%% headers on, but nuke all the default values. (Note that this package
%% *has* to load after the geometry package!)


%%% Edited 6/6/2014

\usepackage[top=2.7cm, bottom = 5.4cm, left=2.72cm, right = 3.0cm]{geometry}
\headsep = 0.7cm
\headheight = 1.0cm 
\footskip = 1.0cm
\voffset = -0.74 cm 
%%%%

\usepackage{fancyhdr}
\pagestyle{fancy}
%\fancyhf{}



%% Now begin customising things. See the fancyhdr docs for more info.

%\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{#1}}{}}
\renewcommand{\sectionmark}[1]{\markright{\MakeUppercase{#1}}{}}
\renewcommand{\headrulewidth}{0pt}
% end of customization

% Add the compsocconf option for Computer Society conferences.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}


% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
%\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
\usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  \DeclareGraphicsExtensions{.pdf,.jpeg,.png,.jpg}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
\usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex


% *** MATH PACKAGES ***
%
%\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/


% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/


% *** ALIGNMENT PACKAGES ***
%
\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/


% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.



%\usepackage[caption=false]{caption}
\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.


% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.


% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
%\hyphenation{op-tical net-works semi-conduc-tor}

%%% Edited 6/6/2014
% title page
%\makeatletter
%\def\ps@IEEEtitlepagestyle{%
%\def\@oddhead{\mbox{\centering{\footnotesize{\textit{Hội thảo quốc gia lần thứ XVII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông Đắk Lắk, 30-31/10/2014}}\scriptsize\rightmark \hfil \thepage}}%
%\def\@evenhead{\scriptsize\thepage \hfil \leftmark\mbox{\centering{\footnotesize{\textit{Hội thảo quốc gia lần thứ XVII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông Đắk Lắk, 30-31/10/2014}}}}}%
%}
%}
%\makeatother

\makeatletter
\def\ps@IEEEtitlepagestyle{%
\def\@oddhead{\centering{\mbox{\footnotesize{\textit{\;\;\;\; Hội thảo quốc gia lần thứ XVII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-Đắk Lắk, 30-31/10/2014}}}}%
\def\@evenhead{\centering{\mbox{\footnotesize{\textit{\;\;\;\; Hội thảo quốc gia lần thứ XVII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-Đắk Lắk, 30-31/10/2014}}}}}%
\def\@oddfoot{\scriptsize \thepage \hfil }%
\def\@evenfoot{\scriptsize \hfil \thepage}
}
}
\makeatother



\begin{document}
\pagenumbering{gobble}
\fontsize{10}{12}
\selectfont

% customizing header/footer via fancyhdr by Nguyễn Trường Thắng
%% Configuration of the header strings for the frontmatter pages.
%\fancyhead[RO]{{\footnotesize\rightmark}ABC\hspace{2em}\thepage}
%\setcounter{tocdepth}{2}
%\fancyhead[LE]{\thepage\hspace{2em}ABC\footnotesize{\leftmark}}
%\fancyhead[RE,LO]{}
%\fancyhead[RO]{{\footnotesize\rightmark}\hspace{2em}\thepage}

%% Configuration of the header strings for the main manuscript pages.
\fancyhead[RE,LO]{\centering{\footnotesize{\textit{Hội thảo quốc gia lần thứ XVII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông Đắk Lắk, 30-31/10/2014}}}}
% end of customization

%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{Một phương pháp xác định ảnh hưởng của trục xương với các điểm biên của vật thể 3D}


% author names and affiliations
% use a multiple column layout for up to two different
% affiliations

\author{\IEEEauthorblockN{Trần Xuân Huy}
\IEEEauthorblockA{LSIS Lab\\Đại học Aix-Marseille, Pháp\\
Email: tranxuanhuy1@gmail.com}
\and
\IEEEauthorblockN{Nguyễn Tấn Khôi}
\IEEEauthorblockA{DATIC Lab\\Đại học Đà Nẵng\\
Email: ntkhoi@dut.udn.vn}
\and
\IEEEauthorblockN{Eric Remy}
\IEEEauthorblockA{LSIS Lab\\Đại học Aix-Marseille, Pháp\\
Email: eric.remy@univ-amu.fr}
}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
%
%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3},
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}


% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle


\begin{abstract}
Trục xương (Medial Axis - MA), được xây dựng từ tập điểm trung tâm của các quả bóng cực đại, dùng để mô tả và phân tích vật thể 2D hoặc 3D. Trục xương đóng vai trò quan trọng trong việc mô tả hình dạng đặc trưng vì vẫn giữ được các đặc tính  của vật thể khi đã xóa bỏ hầu hết các thành phần biên. Trục xương được tính dựa trên chuyển đổi khoảng cách, trong đó mỗi điểm được gán nhãn dựa vào khoảng cách từ điểm đó đến tới nền của ảnh. Nhiều phương pháp cho phép tính toán chuyển đổi bình phương khoảng cách Euclide theo thời gian tuyến tính và trong không gian n chiều. Sau đó, để tính các đặc trưng trích xuất MA từ SEDT, phương pháp kiểm tra cục bộ và Bảng tìm kiếm (Look-Up Table - LUT) cho kết quả tốt hơn hẳn. Trong bài báo này, chúng tôi trình bày hướng nghiên cứu sử dụng thuật toán được trình bày trong \cite{Remy2002649,Remy2005167} để tính toán trục xương cho vật thể trong không gian n chiều với khoảng cách Euclide, đồng thời đánh giá mối quan hệ giữa trục xương và biên của vật thể trong khoảng cách Euclide.

\end{abstract}

\begin{IEEEkeywords}
Medial axis; Centres of maximal disks; Look-up tables; Squared euclidean distance transform; Digital shape representation

\end{IEEEkeywords}


% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Giới thiệu}
% no \IEEEPARstart
Trong phân tích xử lý ảnh, nhiều nghiên cứu về nhận dạng vật thể được quan tâm và triển khai, đặc biệt là trong không gian 2D. Để xác định hình dạng vật thể, người ta thường đi tìm các dạng đặc trưng của vật thể. Trục xương của một vật thể 3D được xác định dựa trên tập hợp tâm của các quả bóng cực đại nằm trong vật thể đó. Có ba phương pháp để tính toán trục xương từ ảnh chuyển đổi khoảng cách của một vật thể: Phương pháp cực đại cục bộ \cite{Rosenfeld:1966:SOD:321356.321357}, phương pháp quả bóng tương đương \cite{Arcelli1988361} và phương pháp bảng tìm kiếm \cite{Borgefors91b}. Tuy nhiên, mỗi phương pháp đều tồn tại nhiều vấn đề \cite{remy2001normes} . Trong \cite{Thiel_these}, tác giả Thiel đã đề xuất một phương pháp mới hiệu quả để tính toán bảng tìm kiếm $Lut$ , và Remy đã đề xuất tính toán cho vùng kiểm tra lân cận $\mathcal{M}_{Lut}$ \cite{remy2001normes}. Trong bài báo này, chúng tôi đề xuất một phương pháp tính toán trục xương cho vật thể và xác định mối quan hệ giữa trục xương này với biên của vật thể.

Bố cục của bài báo bao gồm 5 phần. Phần mở đầu giới thiệu tổng quan về vấn đề nghiên cứu. Phần 2 trình bày một số định nghĩa cần thiết, cách xây dựng bảng tìm kiếm $LUT$ và vùng kiểm tra lân cận $\mathcal{M}_{Lut}$. Phần 3 trình bày đóng góp của chúng tôi: phương pháp xác định quan hệ giữa trục xương và biên của vật thể. Kết quả cho trường hợp 2D trong phần 4, cuối cùng là kết luận và hướng nghiên cứu tiếp tục.

%\section{Chuyển đổi khoảng cách Euclide}
\section{Xây dựng trục xương}
Việc trích xuất MA từ một vật thể có thể chia thành các bước như sau. Đầu tiên cần tính chuyển đổi khoảng cách Euclide SEDT, sau đó xây dựng bảng tìm kiếm $LUT$ và vùng kiểm tra lân cận $\mathcal{M}_{Lut}$. Cuối cùng, sử dụng $LUT$ và $\mathcal{M}_{Lut}$ xây dựng được để trích xuất MA.

\subsection{Khoảng cách Euclide}
Khoảng cách Euclide $d_E$ giữa hai điểm được tính toán dựa trên hàm bình phương khoảng cách $d_E^2$. Trên mặt lưới rời rạc, khoảng cách Euclide giữa hai điểm $P_1 = (x_1,y_1)$ và $P_2 = (x_2,y_2)$ được xác định \cite{Saito19941551}:
\begin{align*}
d_E(P_1,P_2) &= \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} \\
d_E^2(P_1,P_2) &= {(x_2-x_1)^2+(y_2-y_1)^2}
\end{align*}

% Thực vây, mặc dù hàm này không được coi là một khoảng cách (ví dụ phản chứng Hình \ref{fig:dE2-InegaliteTriangulaire} trong \cite{remy2001normes}), tuy nhiên nó có tất cả thuộc tính cần thiết được mô tả trong chương kế tiếp.
%
%\begin{figure}[!htb])
%\centering
%  \includegraphics[width=0.7\linewidth]{figs/dE2-InegaliteTriangulaire}
%  \caption{Hàm $d_E^2$ không tuân theo bất đẳng thức tam giác: $d_E^2(A,C)$ không bé hơn hoặc bằng tổng $d_E^2(A,B)+d_E^2(B,C)$.}\label{fig:dE2-InegaliteTriangulaire}
%\end{figure}

\subsection{Chuyển đổi khoảng cách Euclide SEDT}
Một ảnh $I$ được gọi là ảnh nhị phân nếu trong ảnh chỉ tồn tại hai giá trị khác nhau: 0 và 1. Tập hợp $F$ những điểm có giá trị 1 biểu diễn vật thể, và tập $\overline{F}$ những điểm có giá trị 0 biểu diễn phần nền.

Chuyển đổi khoảng cách, được thực hiện bằng cách gán nhãn mỗi điểm của vật thể bằng với khoảng cách tới điểm gần nhất nằm trong phần bù của vật thể. Do đó, một điểm $p$ của vật thể $F$ được xác định:
\[DT(p) = \min\left\lbrace d(p,q) \enspace : \enspace \forall q \in \overline{F}\right\rbrace \]

với DT là hàm chuyển đổi khoảng cách. Để tính toán $d_E^2$, ta dựa trên chuyển đổi khoảng cách được đề xuất trong \cite{Saito19941551}. Xem một ảnh ba chiều được biểu diễn bởi $F = \left\lbrace f_{ijk} \right\rbrace $, trong đó $f_{ijk}$ là giá trị của điểm ảnh $(i,j,k)$ (Hình \ref{fig:3dDigitialPicture}). Giả sử ảnh có \textsl{L} hàng, M cột và N mặt phẳng.

\begin{figure}[!htb]
\centering
  \includegraphics[width=0.5\linewidth]{figs/3dDigitialPicture}
  \caption{Một ảnh số ba chiều.}\label{fig:3dDigitialPicture}
\end{figure}

Gọi $S = \left\lbrace s_{ijk} \right\rbrace $ là ảnh bình phương khoảng cách Euclide của một ảnh nhị phân. Do đó, giá trị $s_{ijk}$ được xác định bởi khoảng cách tối thiểu từ điểm ảnh $(i,j,k)$ đến điểm ảnh gần nhất nằm trong nền của vật thể:

\begin{multline}
s_{ijk} = \min_{(p,q,r)}\lbrace d_E^2((i,j,k),(p,q,r))^2   : \\  f_{pqr}=0,  1\leqslant p \leqslant L, 1 \leqslant q \leqslant M, 1 \leqslant r \leqslant N \rbrace
\end{multline}

\begin{multline}
\quad \enspace =\min_{(p,q,r)}\lbrace (i-p)^2+(j-q)^2+(k-r)^2  : \\ f_{pqr}=0,  1\leqslant p \leqslant L, 1 \leqslant q \leqslant M, 1 \leqslant r \leqslant N \rbrace
\end{multline}

%\begin{align}
%s_{ijk} &= \min_{(p,q,r)}\lbrace d_E^2((i,j,k),(p,q,r))^2 \enspace : \enspace  f_{pqr}=0, \enspace 1\leqslant p \leqslant L, 1 \leqslant q \leqslant M, 1 \leqslant r \leqslant N \rbrace \\ 
%&=\min_{(p,q,r)}\lbrace (i-p)^2+(j-q)^2+(k-r)^2 \enspace : \enspace f_{pqr}=0, \enspace 1\leqslant p \leqslant L, 1 \leqslant q \leqslant M, 1 \leqslant r \leqslant N \rbrace
%\end{align}

\subsection{Mặt nạ và phát sinh mặt nạ cho điểm ảnh}
Một mặt nạ $\mathcal{M}$ là một tập hợp đối xứng tâm của $m$ véc tơ không rỗng $\overrightarrow{v} \in \mathbb{E}^*$. Có nghĩa là, với mỗi véc tơ $\overrightarrow{v_i}$, tồn tại một véc tơ $\overrightarrow{v_j}$ mà $\overrightarrow{v_j}=-\overrightarrow{v_i}$ \cite{remy2001normes}.

Một mặt nạ cho phép thể hiện các điểm $p+\overrightarrow{v_i}$ bằng cách xem xét xung quanh một điểm $p$ cho trước, điểm này sẽ thay đổi trong suốt một thuật toán.

\begin{figure}[!htb]
\centering
  \includegraphics[width=0.8\linewidth]{figs/regionZ}
  \caption{Các vùng $\frac{1}{8}\mathbb{Z}^2$ và $\frac{1}{48}\mathbb{Z}^3$.}\label{fig:regionZ}
\end{figure}
Phát sinh mặt nạ là tập hợp con của mặt nạ hoàn chỉnh $\mathcal{M}$ nằm trong vùng $\frac{1}{8}\mathbb{Z}^2$ (hoặc $\frac{1}{48}\mathbb{Z}^3$, Hình \ref{fig:regionZ}), gọi chung là vùng $G(\mathbb{Z}^n)$; được ký hiệu $\mathcal{M}^g$. Tập hợp con này cho phép tái tạo mặt nạ gốc một cách chính xác nhờ sự đối xứng. Ta có giá trị $\mathcal{M}^g$ trong không gian 2D, 3D như sau:
\[\mathcal{M}^g = \left\lbrace (x_i,y_i) \in \mathcal{M} : (x_i,y_i) \in \frac{1}{8}\mathbb{Z}^2 \right\rbrace , \]
\[\mathcal{M}^g = \left\lbrace (x_i,y_i,z_i) \in \mathcal{M} : (x_i,y_i,z_i) \in \frac{1}{48}\mathbb{Z}^3 \right\rbrace .\]

\subsection{Bóng trực tiếp và bóng đảo ngược}
Đây là một khái niệm đóng vai trò quan trọng trong việc xây dựng bảng tìm kiếm $Lut$ và vùng kiểm tra lân cận $\mathcal{M}_{Lut}$. Ta gọi bóng trực tiếp $B_d$ và đảo ngược $B_d^{-1}$ tâm $p$ bán kính $r$ trong không gian Euclide, tập hợp các điểm $q$ được xác định lần lượt như sau:
\[B_d{(p,r)} = \left\lbrace q \in \mathbb{E} \: : \: d(p,q) \leqslant r \right\rbrace \]
\[B_d^{-1}(p,r) = \left\lbrace q \in \mathbb{E} : r-d(p,q) > 0 \right\rbrace \]

Vì $d_E^2$ là một hàm số nguyên, nên bóng trực tiếp và bóng đảo ngược có mối quan hệ \cite{Thiel_these}:
\begin{align} 
\label{eq:lemme}
B_d(p,r) = B_d^{-1}(p,r+1).
\end{align}

\subsection{Bảng tìm kiếm $LUT$}
Ta gọi $\mathcal{M}_{Lut}$ là tập véc tơ đối xứng tâm, $\mathcal{M}_{Lut}^g$ là tập con của $\mathcal{M}_{Lut}$ trong vùng $\frac{1}{8}\mathbb{Z}^2$ (hoặc $\frac{1}{48}\mathbb{Z}^3$). $\overrightarrow{v}^g \in \mathcal{M}_{Lut}^g$ là véc tơ phát sinh của véc tơ bất kỳ $\overrightarrow{v} \in \mathcal{M}_{Lut}$ \cite{remy2001normes}.

Một điểm ảnh $p$ là tâm của một đĩa cực đại nếu không có điểm ảnh $q$ nào khác thỏa mãn bóng $B_d^{-1}(q,DT[q])$ bao phủ toàn bộ $B_d^{-1}(p,DT[p])$. Trong trường hợp này, ta nói sự xuất hiện của $q$ ngăn không cho $p$ trở thành điểm trục xương. Giả sử rằng ta tìm được $q$ trong vùng lân cận $\mathcal{M}_{Lut}$ của $p$. Cũng giả sử rằng, với mỗi giá trị $DT[p]$, ta tìm được giá trị nhỏ nhất $DT[q]$ sao cho $q$ ngăn không cho $p$ trở thành điểm trục xương theo hướng $\overrightarrow{v}=\overrightarrow{pq}$; giá trị nhỏ nhất này được lưu trong một bảng tìm kiếm Lut. Giá trị nhỏ nhất ứng với $p$ và $\overrightarrow{v}$ được lưu tại phần tử $Lut[\overrightarrow{v}][DT[p]]$ của bảng. Vì tính chất đối xứng, ta chỉ cần lưu giá trị liên quan trong $\mathcal{M}_{Lut}^g$; do đó giá trị nhỏ nhất ứng với $p$ và $\overrightarrow{v}$ được lưu tại $Lut[\overrightarrow{v}^g][DT[p]]$. Cuối cùng ta có điều kiện sau đây:

\begin{multline}
p \in MA \Longleftrightarrow DT[p+\overrightarrow{v}] < Lut[\overrightarrow{v}^g][DT[p]], \\
\forall \overrightarrow{v} \in \mathcal{M}_{Lut}
\end{multline}

%\[p \in MA \Longleftrightarrow \forall \overrightarrow{v} \in \mathcal{M}_{Lut}, DT[p+\overrightarrow{v}] < Lut[\overrightarrow{v}^g][DT[p]]\]

%\section{Xây dựng bảng tìm kiếm $Lut$ và vùng kiểm tra lân cận $\mathcal{M}_{Lut}$ cho SEDT}
\subsection{Tính toán một phần tử của Lut}
Việc tính toán một phần tử $Lut[\overrightarrow{v}][r]$ trong bảng $Lut$ ứng với $r=DT[p]$ theo hướng $\overrightarrow{v}$, bao hàm việc tìm bán kính nhỏ nhất $R$ của quả bóng $B^{-1}(p+\overrightarrow{v},R)$ bao phủ hoàn toàn $B^{-1}(p,r)$ (Hình \ref{fig:maximumLocal}). Để tìm $R$, ta sử dụng mối quan hệ (\ref{eq:lemme}), và một ảnh khoảng cách khác, ký hiệu $CT^g$, là kết quả của việc chuyển đổi khoảng cách đến gốc, trong đó mỗi điểm của $G(\mathbb{Z}^n)$ được gán nhãn bằng khoảng cách từ điểm đó đến gốc (ví dụ Hình \ref{fig:bouleDirect103}).
\begin{figure}[]
\centering
  \includegraphics[width=0.5\linewidth]{figs/maximumLocal}
  \caption{Quả bóng tâm $p$ bị bao phủ bởi một quả bóng khác.}\label{fig:maximumLocal}
\end{figure}

%\begin{figure}
%  \centering           
%  \subfloat[]{\label{fig:recouvrementDeuxBoule}\includegraphics[width=0.23\textwidth]{figs/recouvrementDeuxBoule}} 
%  \hspace*{1.3em}
%  \subfloat[]{\label{fig:recouvrementTranslate}\includegraphics[width=0.23\textwidth]{figs/recouvrementTranslate}}
%  \caption{Kiểm tra sự bao phủ của hai quả bóng trong vùng $\frac{1}{8}\mathbb{Z}^2$.}
%  \label{fig:lesBoules}
%\end{figure}

%\begin{figure}[]
%\centering
%  \includegraphics[width=0.6\linewidth]{figs/recouvrementDeuxBoule}
%  \caption{Kiểm tra sự bao phủ của hai quả bóng trong vùng $\frac{1}{8}\mathbb{Z}^2$.}\label{fig:recouvrementDeuxBoule}
%\end{figure}
%
\begin{figure}[]
\centering
  \includegraphics[width=0.6\linewidth]{figs/recouvrementTranslate}
  \caption{Kiểm tra sự bao phủ sau khi chuyển đổi khoảng cách đến gốc $CT^g$.}\label{fig:recouvrementTranslate}
\end{figure}

%\begin{figure}[]
%\centering
%  \includegraphics[width=1\linewidth]{figs/compCTg}
%  \caption{Thuật toán chuyển đổi khoảng cách đến gốc}\label{fig:compCTg}
%\end{figure}

% Insert the algorithm

%\begin{algorithm}
%\scriptsize
%\caption{Chuyển đổi khoảng cách đến gốc}
%\label{compCTg}
%\begin{algorithmic}[1]
%\Procedure{CompCTg}{$L,CT^g$}
%	\For{$x_1=0$ \textbf{to} $L-1$, \textbf{for} $x_2=0$ \textbf{to} $x_1$, $\dots$, \textbf{for} $x_n=0$ \textbf{to} $x_{n-1}$}
%	\State $CT^g[x_1,\dots,x_n]=x_1^2+\dots+x_n^2;$
%	\EndFor
%\EndProcedure
%\end{algorithmic}
%\end{algorithm}

\begin{figure}
  \centering           
  \subfloat[]{\label{fig:bouleDirect103}\includegraphics[width=0.23\textwidth]{figs/bouleDirect103}} 
  \hspace*{1.3em}
  \subfloat[]{\label{fig:bouleInverse104}\includegraphics[width=0.23\textwidth]{figs/bouleInverse104}}
  \caption{Bóng trực tiếp B(103) ở (a) và bóng đảo ngược $B^{-1}\left(104\right)$ ở (b) chứa cùng số điểm.}
  \label{fig:lesBoules}
\end{figure}

Sự bao phủ của bóng $B^{-1}(q,R_+)$ lên bóng $B^{-1}(p,r)$ được kiểm tra bằng cách quét ảnh $CT^g$; hơn nữa, bán kính nhỏ nhất $R$ có thể được tìm trong $CT^g$ trong khi quét. Ta áp dụng chuyển đổi khoảng cách đến gốc như Hình \ref{fig:recouvrementTranslate}. Quét mỗi điểm $p_1$ của $G(B^{-1}(O,r))$, với dịch chuyển theo véc tơ $\overrightarrow{v}^g$ cho ta $p_2$. Giá trị $d_E^2(O,p_1)$ và $d_E^2(O,p_2)$ được đọc trong $CT^g$. Ta có:
\begin{align}
\label{eq:relationp1p2}
R = max\left\lbrace d_E^2(O,p_1+\overrightarrow{v}^g):p_1 \in G(B^{-1}(O,r) \right\rbrace.
\end{align}

%Phương thức này có thể được hiện thực vì tất cả quan hệ bao phủ có thể được tìm thấy trong cùng lần quét. Với mỗi điểm $p_1$, ta tìm bán kính tương ứng $r_1=CT^g[p_1]+1$ bởi đẳng thức \ref{eq:lemme}. Sau đó ta tìm bán kính $r_2$ của quả bóng có tâm là $p_2$ tương ứng. Giá trị của $r_2$ là $CT^g[p_2]+1=CT^g[p_1+\overrightarrow{v}^g]+1$ bởi đẳng thức \ref{eq:lemme}. Trong quá trình quét, $Lut[\overrightarrow{v}^g][r_1]$ giữ giá trị lớn nhất tìm được của $r_2$, đến cuối cùng chính là giá trị $R$ (biểu thức \ref{eq:relationp1p2}).

%\begin{figure}[]
%\centering
%  \includegraphics[width=1\linewidth]{figs/calculLutCol}
%  \caption{Thuật toán tính toán một cột của bảng tìm kiếm $Lut$}\label{fig:calculLutCol}
%\end{figure}

\subsection{Tính toán $\mathcal{M}_{Lut}$}
Ta giả định rằng $\mathcal{M}_{Lut}^g$ cho trước là đủ để trích xuất chính xác MA từ bất kỳ ảnh DT có giá trị không quá $R_{Known}$. Nghĩa là $\mathcal{M}_{Lut}^g$ này cho phép trích xuất, từ bấy kỳ quả bóng $B(O,R)$ với $R\leq R_{Known}$, một MA mà theo định nghĩa, là điểm duy nhất $O$. Ban đầu, $\mathcal{M}_{Lut}^g$ rỗng và $R_{Known}=0$.

Tăng $R_{Known}$ đến $R_{Target}$ cho trước. Với mỗi bước tăng của $R$, ta trích xuất ảnh DT và sau đó là MA của quả bóng $B(O,R)$, đến khi hoặc $R$ đạt $R_{Target}$, hoặc phát hiện một điểm khác $O$ trong ảnh MA của $B(O,R)$. Nếu $R$ đạt $R_{Target}$, ta biết rằng $\mathcal{M}_{Lut}^g$ cho phép trích xuất chính xác MA, với bất kỳ DT chứa giá trị nhỏ hơn hoặc bằng $R_{Target}$. Do đó, giá trị $R_{Target}$ này được lưu như là $R_{Known}$ mới.

Ngược lại, nếu một điểm $p$ được tìm thấy ở MA trong quá trình quét, thì $\mathcal{M}_{Lut}^g$ không đủ để trích xuất chính xác MA. Trong trường hợp này, ta thêm một véc tơ mới $\overrightarrow{Op}$ vào $\mathcal{M}_{Lut}^g$ nhằm xây dựng quả bóng $B(O,R)$ bao phủ $B^{-1}(p,DT^g[p])$. 

%Véc tơ này là điều kiện cần và đủ để loại bỏ $p$ khỏi MA của quả bóng $B(O,R)$ vì $\mathcal{M}_{Lut}^g$ hiện tại đã đúng đến $R-1$; nên $\mathcal{M}_{Lut}^g$ cho phép tìm tất cả các bóng trực tiếp bao phủ $B^{-1}(p,DT^g[p])$ với bán kính nhỏ hơn hoặc bằng $R-1$. Do đó, quả bóng duy nhất chưa kiểm tra là $B(O,R)$. Quả bóng này ở theo hướng $\overrightarrow{pO}$ từ $p$ và phải được tìm thấy bởi $\mathcal{M}_{Lut}^g$ để loại bỏ $p$. Vì $\mathcal{M}_{Lut}^g$ đối xứng, nên $B(O,R)$ được xác định bằng cách thêm $\overrightarrow{Op}$ vào $\mathcal{M}_{Lut}^g$.

%Sau khi thêm véc tơ vào $\mathcal{M}_{Lut}^g$, ta tính cột mới tương ứng trong bảng tìm kiếm $Lut$ (dòng 18). Sau đó, ta đảm bảo rằng $\mathcal{M}_{Lut}^g$ mới là đủ để loại bỏ $p$ (dòng 19).

Khi $p$ đã bị loại bỏ, ta tiếp tục thủ tục quét với $R$ hiện tại. Những điểm $p$ khác có thể được tìm thấy liên tục, mỗi lần như vậy, ta có một véc tơ và cột $Lut$ mới. Việc tính toán $\mathcal{M}_{Lut}^g$ kết thúc khi $R$ đạt $R_{Target}$.

%\begin{figure}[]
%\centering
%  \includegraphics[width=1\linewidth]{figs/calculEtVerifieLut}
%  \caption{Thuật toán tính bảng tìm kiếm $Lut$ hoàn chỉnh và xây dựng $\mathcal{M}_{Lut}^g$.}\label{fig:calculEtVerifieLut}
%\end{figure}

% Insert the algorithm
%\begin{algorithm*}
%\scriptsize
%\caption{Xây dựng bảng tìm kiếm $Lut$ và vùng kiểm tra $\mathcal{M}_{Lut}^g$ hoàn chỉnh}
%\label{calculEtVerifieLut}
%\begin{algorithmic}[1]
%\Procedure{CompLutMask}{$L,\mathcal{M}_{Lut}^g,R_{Known},R_{Target},Lut$}
%	\State $CompCTg(L,CT^g)$
%	\For{\textbf{each} $\overrightarrow{v}^g$ in $\mathcal{M}_{Lut}^g$}
%	\State $CompLutCol(CT^g,L,\overrightarrow{v}^g,R_{Target},Lut[\overrightarrow{v}^g])$
%	\EndFor
%		\For{$R=R_{Known}+1$ \textbf{to} $R_{Target}$}
%			\For{$x_1=0$ \textbf{to} $L-1$, \textbf{for} $x_2=0$ \textbf{to} $x_1$, $\dots$, \textbf{for} $x_n=0$ \textbf{to} $x_{n-1}$}
%	\If {$CT^g[x_1,\dots,x_n] \leq R$} 
%	\State $DT^g[x_1,\dots,x_n]=1$
%	\Else \State $DT^g[x_1,\dots,x_n]=0$
%	\EndIf
%	\EndFor
%	\State $CompSEDTg(L,DT^g)$
%	
%	\For{$x_1=1$ \textbf{to} $L-1$, \textbf{for} $x_2=0$ \textbf{to} $x_1$, $\dots$, \textbf{for} $x_n=0$ \textbf{to} $x_{n-1}$}
%	\If {$DT^g[x_1,\dots,x_n] \neq 0$ \textbf{and} $IsMAg((x_1,\dots,x_n),\mathcal{M}_{Lut}^g,Lut,DT^g)$} 
%	\State $\mathcal{M}_{Lut}^g = \mathcal{M}_{Lut}^g \cup (x_1,\dots,x_n;R)$
%	\State $CompLutCol(CT^g,L,(x_1,\dots,x_n),R_{Target},Lut[x_1,\dots,x_n])$
%	\If {$IsMAg((x_1,\dots,x_n),\mathcal{M}_{Lut}^g,Lut,DT^g)$}
%	\State \textbf{error}
%	\EndIf
%	\EndIf
%	
%	\EndFor
%	\EndFor
%
%
%\EndProcedure
%\end{algorithmic}
%\end{algorithm*}

%\subsection{Kết quả }
%Ta thấy kết quả của phương thức xây dựng $\mathcal{M}_{Lut}^g$ ở Hình \ref{fig:mglutz2} cho khoảng cách 2D. Bảng này cũng lưu giữ bán kính xuất hiện $R$ ứng với từng véc tơ. Giá trị $R$ cho phép giới hạn số véc tơ cần kiểm tra với mỗi điểm trong quá trình trích xuất MA. Trong một DT với giá trị lớn nhất là $R_{max}$, cần và đủ chỉ lấy tập con $\mathcal{M}_{Lut}^{R_{max}}=\left\lbrace  (\overrightarrow{v};R) \in \mathcal{M}_{Lut}:R<R_{max}\right\rbrace $ làm vùng kiểm tra lân cận để tìm được tất cả điểm trung tâm MA.

Việc trích xuất MA từ một ảnh nhị phân $I$ có thể chia thành các bước. Đầu tiên cần tính SEDT, sau đó tìm $R_{max}$ trong ảnh DT kết quả. Tiếp theo, CompLutMask được áp dụng với $R_{Target}=R_{max}$; bước này có thể không cần thiết nếu một $\mathcal{M}_{Lut}^g$ đầy đủ đã được lưu. Tập con $\mathcal{M}_{Lut}^{R_{max}}$ sau đó được sử dụng để trích xuất MA.

\section{Xác định ảnh hưởng giữa trục xương và biên của vật thể}
%\subsection{Giới thiệu}

\begin{figure}
  \centering           
  \subfloat[]{\label{fig:noise1}\includegraphics[width=0.22\textwidth]{figs/noise1}} 
  \hspace*{1.3em}
  \subfloat[]{\label{fig:noise2}\includegraphics[width=0.22\textwidth]{figs/noise2}}
  \caption{(a): Vật thể (màu xám) và trục xương (màu đen); (b) cùng một vật thể, nhưng với một ít nhiễu thêm vào ở biên. trục xương trở nên phức tạp hơn nhiều so với Hình (a) \cite{Michal2013}.}
  \label{fig:noise}
\end{figure}

\begin{figure}[H]
\centering
  \includegraphics[width=0.6\linewidth]{figs/medialaxisbasic}
  \caption{Ví dụ vật thể và trục xương.}\label{fig:medialaxisbasic}
\end{figure}

Trục xương sẽ biến động khi vật thể có sự thay đổi hình dạng: thay đổi nhỏ vật thể có thể dẫn đến sự thay đổi đáng kể giữa các trục xương (Hình \ref{fig:noise}). Vì vậy, cần lọc nhiễu trước khi tính toán trục xương.

Có nhiều cách khác nhau để giải quyết. Đơn giản nhất chỉ giữ các điểm là tâm của đĩa cực đại có đường kính lớn hơn một giá trị cho trước. Một giải pháp phức tạp hơn: đếm số điểm vật thể nằm trong một quả bóng nhưng không nằm trong những quả bóng khác; điểm trung tâm sẽ bị xóa nếu vùng bao phủ của bóng tương ứng quá nhỏ \cite{Michal2013}.

%\subsection{Thuật toán xác định mối quan hệ giữa trục xương và biên vật thể}
Thuật toán \ref{BordEtMA} cho phép xác định mối quan hệ giữa những điểm của trục xương và những điểm ở biên vật thể:

\begin{itemize}
\item Với một điểm ở biên, tìm những điểm của trục xương ngăn điểm này trở thành một phần của trục xương.
\item Với một điểm của trục xương, tìm những điểm ở biên bị ngăn bởi điểm này.
\end{itemize}

%\begin{figure}[]
%\centering
%  \includegraphics[width=1.2\linewidth]{figs/BordEtMA}
%  \caption{Thuật toán xác định mối quan hệ giữa trục xương và biên vật thể.}\label{fig:BordEtMA}
%\end{figure}
 
% Insert the algorithm
\begin{algorithm}
\scriptsize
\caption{Xác định mối quan hệ giữa trục xương và biên vật thể}
\label{BordEtMA}
\begin{algorithmic}[1]
\Procedure{RelationEntreBordEtMA}{$orig,road,result$}
	\State $queue.push(orig)$
	\State $road[orig].push(orig,\overrightarrow{0})$
	\While{$queue.notEmpty()$}
		\State $p \gets queue.pop()$
		\If{$passed[p]=0$} 
		\If{$\mathcal{M}_{Lut}[p].empty()$} 
		\State $result[orig] \gets result[orig] \cup road[p]$

		\Else 
		\For{\textbf{each} $(\overrightarrow{v},w)$ in $\mathcal{M}_{Lut}[p]$}
		\State
		$p' \gets p+\overrightarrow{v}$
		\If {$passed[p']=0$}
		\State $queue.push(p')$
		\State $road[p'] \gets road[p]+(p',\overrightarrow{v})$
		
		\EndIf
		\EndFor
		\EndIf
		\State $passed[p] \gets 1$
		\EndIf
	\EndWhile

\EndProcedure
\end{algorithmic}
\end{algorithm}

Thuật toán dựa trên thuật toán tìm kiếm cây nhị phân theo chiều rộng (Breadth First Search - BFS). Thuật toán BFS cho phép duyệt cây nhị phân theo cách thức liên tục, bằng cách sử dụng một hàng đợi. Các bước của thuật toán BFS:

\begin{enumerate}
\item    Đặt nút khởi đầu vào hàng đợi.
\item    Lấy nút ở đầu hàng đợi ra khỏi hàng đợi và kiểm tra.
\item    Đặt tất cả nút con chưa kiểm tra vào cuối hàng đợi.
\item    Nếu hàng đợi không rỗng, quay lại bước 2.
\end{enumerate}

\begin{figure}[H]
\centering
  \includegraphics[width=0.4\linewidth]{figs/grapheBFS}
  \caption{Duyệt nút trên cây tìm kiếm nhị phân theo chiều rộng theo thứ tự A, B, C, E, D, F, G.}\label{fig:grapheBFS}
\end{figure}

Với thuật toán \ref{BordEtMA} được đề xuất, điểm ở biên được kiểm tra là nút khởi đầu, điểm trục xương là nút kết thúc.

%Các biến số chính của thuật toán:
%
%\begin{itemize}
%\item Điểm $orig$ là điểm ở biên của ảnh khoảng cách $DT$ mà ta sẽ kiểm tra. Đây cũng là nút khởi đầu trong hàng đợi.
%\item Ảnh $submasque$, mỗi điểm $p$ của ảnh chứa một tập con của $\mathcal{M}_{Lut}$, ký hiệu $\mathcal{M}_{Lut}[p]$, cấm $p$ trở thành một phần của trục xương, nghĩa là những thỏa mãn điều kiện sau:
%\begin{equation} \label{critereMA}
%\overrightarrow{v} \in \mathcal{M}_{Lut}, DT[p+\overrightarrow{v}] \geq Lut[\overrightarrow{v}^g][DT[p]]
%\end{equation}
%\item Ảnh $road$, mỗi điểm $q$ của ảnh chứa một con đường từ $orig$ đến $q$. Ta gọi $q_A=(x_A,y_A,z_A)$ là vị trí điểm $A$ trong ảnh gốc 3D, và $\overrightarrow{v_A} \in \mathcal{M}_{Lut}$. Ta xem rằng một con đường là một chuỗi $(q_1,\overrightarrow{v_1}),\dots,(q_k,\overrightarrow{v_k})$. Hai điểm liên tiếp $q_i$ và $q_{i+1}$ thỏa mãn: $q_{i+1}$ ngăn $q_i$ trở thành điểm trục xương theo hướng $\overrightarrow{v_{i+1}}$. Do đó, với một con đường, khởi đầu là điểm ở biên $orig$, kết thúc là một điểm trục xương.
%\item Ảnh nhị phân $passed$ để đánh dấu nếu một điểm đã được thăm bởi thuật toán, nghĩa là một điểm chỉ được thêm vào hàng đợi một lần duy nhất.
%\item Ảnh $result$, mỗi điểm $q$ chứa những con đường từ $q$ đến những điểm trục xương mà ngăn $q$ trở thành điểm trục xương. Ta chỉ tính một con đường cho một cặp \textit{q-điểm trục xương}.
%\end{itemize}

Việc tính toán này cho phép xác định độ quan trọng của một điểm trục xương. Một điểm trục xương là quan trọng nếu điểm này ngăn nhiều điểm biên trở thành điểm trục xương. Hơn nữa, ta có thể giải quyết vấn đề đơn giản hóa trục xương với câu hỏi: đâu là tập con nhỏ nhất của trục xương mà không thay đổi (hoặc thay đổi ít) vật thể $S$ khi tiến hành tái tạo vật thể.

\section{Kết quả thực nghiệm}
Trong phần này, chúng tôi trình bày kết quả chuyển đổi khoảng cách và trích xuất trục xương với bình phương khoảng cách Euclide $d_E^2$, cách xác định độ quan trọng của một véc tơ trong mặt nạ, và mối quan hệ giữa trục xương và biên vật thể. Dữ liệu vào là ảnh nhị phân $n$ chiều và tập các véc tơ lưu trong $\mathcal{M}_{Lut}^g$. Ví dụ, ảnh 2D là một hình vuông cạnh 256 (chứa 65536 điểm ảnh), vật thể chứa 16096 điểm ảnh (Hình \ref{fig:origingoniol}). Tập các véc tơ lưu trong $\mathcal{M}_{Lut}^g$ được tổ chức như Bảng \ref{fig:mglutz2}.

%\begin{figure}[!htb]
%\centering
%  \includegraphics[width=0.6\linewidth]{figs/mglutz2}
%  \caption{$\mathcal{M}_{Lut}^g$ cho khoảng cách 2D $d_E^2$}\label{fig:mglutz2}
%\end{figure}

\begin{table}[ht]
\scriptsize
\begin{minipage}[b]{1\linewidth}\centering
\begin{tabular}{|cccc|}
\hline 
i & x & y & R \\ 
\hline 
1 & 1 & 0 & 1 \\ 

2 & 1 & 1 & 2 \\ 

3 & 2 & 1 & 101 \\ 

4 & 3 & 1 & 146 \\ 

5 & 3 & 2 & 424 \\ 

6 & 4 & 1 & 848 \\ 

7 & 5 & 1 & 1370 \\ 
\hline 
\end{tabular} 
\end{minipage}
\caption{$\mathcal{M}_{Lut}^g$ cho khoảng cách 2D $d_E^2$.}
\label{fig:mglutz2}
\end{table}

\begin{figure}[H]
  \centering           
  \subfloat[]{\label{fig:origingoniol}\includegraphics[width=0.22\textwidth]{figs/origingoniol}}
  \hspace*{1.3em}
  \subfloat[]{\label{fig:distancemapgoniol}\includegraphics[width=0.22\textwidth]{figs/distancemapgoniol}}
  
  \subfloat[]{\label{fig:medialaxisgoniol}\includegraphics[width=0.22\textwidth]{figs/medialaxisgoniol}}
  \caption{Ví dụ 2D: vật thể (a), ảnh khoảng cách DT với $d_E^2$ (b) và trục xương với $d_E^2$ (c).}
  \label{fig:goniol1}
\end{figure}

\subsection{Độ quan trọng của một véc tơ trong mặt nạ}
Để tính độ quan trọng của một véc tơ $\overrightarrow{v}$, ta đếm số lần véc tơ đó thỏa mãn điều kiện:

\begin{equation} \label{critereMA}
\overrightarrow{v} \in \mathcal{M}_{Lut}, DT[p+\overrightarrow{v}] \geq Lut[\overrightarrow{v}^g][DT[p]]
\end{equation}

 khi trích xuất MA. Ta có kết quả tính toán (bảng \ref{doquantrongvecto}) cho hai ảnh khác nhau.

%\begin{figure}
%  \centering           
%  \subfloat[]{\label{fig:esort}\includegraphics[width=0.2\textwidth]{figs/esort}}
%  \hspace*{1.9em}
%  \subfloat[]{\label{fig:negesort}\includegraphics[width=0.2\textwidth]{figs/negesort}}
%  \caption{Độ quan trọng của véc tơ $\mathcal{M}_{Lut}$ trong trích xuất MA với hai ảnh khác nhau (số thứ tự trong $\mathcal{M}_{Lut}$ gốc, số lần sử dụng, tọa độ x, tọa độ y, giá trị véc tơ, số thứ tự véc tơ $\mathcal{M}_{Lut}^g$ tương ứng).}
%  \label{fig:sort}
%\end{figure}
\begin{table}[ht]
\scriptsize
\begin{minipage}[b]{0.45\linewidth}\centering
\begin{tabular}{|c|c|cc|c|c|}
\hline 
5 & 166 & 0 & -1 & 1 & 0 \\ 
\hline 
1 & 163 & 0 & 1 & 1 & 0 \\ 
\hline 
6 & 130 & 1 & -1 & 2 & 1 \\ 
\hline 
2 & 123 & -1 & 1 & 2 & 1 \\ 
\hline 
7 & 117 & -1 & 0 & 1 & 0 \\ 
\hline 
3 & 109 & 1 & 0 & 1 & 0 \\ 
\hline 
0 & 75 & 1 & 1 & 2 & 1 \\ 
\hline 
4 & 68 & -1 & -1 & 2 & 1 \\ 
\hline 
\end{tabular} 
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.45\linewidth}
\centering
\begin{tabular}{|c|c|cc|c|c|}
\hline 
1 & 473 & 0 & 1 & 1 & 0 \\ 
\hline 
6 & 472 & 1 & -1 & 2 & 1 \\ 
\hline 
5 & 454 & 0 & -1 & 1 & 0 \\ 
\hline 
2 & 445 & -1 & 1 & 2 & 1 \\ 
\hline 
3 & 364 & 1 & 0 & 1 & 0 \\ 
\hline 
7 & 361 & -1 & 0 & 1 & 0 \\ 
\hline 
4 & 356 & -1 & -1 & 2 & 1 \\ 
\hline 
0 & 321 & 1 & 1 & 2 & 1 \\ 
\hline 
\end{tabular}
\end{minipage}
\caption{Độ quan trọng của véc tơ $\mathcal{M}_{Lut}$ trong trích xuất MA với hai ảnh khác nhau (số thứ tự trong $\mathcal{M}_{Lut}$ gốc, số lần sử dụng, tọa độ x, tọa độ y, giá trị véc tơ, số thứ tự véc tơ $\mathcal{M}_{Lut}^g$ tương ứng).}
\label{doquantrongvecto}
\end{table}

%\begin{table}
%\tiny
%\centering
%\subfloat[Bảng 1]{%
%\begin{tabular}{|c|c|cc|c|c|}
%\hline 
%5 & 166 & 0 & -1 & 1 & 0 \\ 
%\hline 
%1 & 163 & 0 & 1 & 1 & 0 \\ 
%\hline 
%6 & 130 & 1 & -1 & 2 & 1 \\ 
%\hline 
%2 & 123 & -1 & 1 & 2 & 1 \\ 
%\hline 
%7 & 117 & -1 & 0 & 1 & 0 \\ 
%\hline 
%3 & 109 & 1 & 0 & 1 & 0 \\ 
%\hline 
%0 & 75 & 1 & 1 & 2 & 1 \\ 
%\hline 
%4 & 68 & -1 & -1 & 2 & 1 \\ 
%\hline 
%\end{tabular} 
%}%
%\quad\quad% --- set horizontal distance between tables here
%\subfloat[Bảng 2]{%
%\begin{tabular}{|c|c|cc|c|c|}
%\hline 
%1 & 473 & 0 & 1 & 1 & 0 \\ 
%\hline 
%6 & 472 & 1 & -1 & 2 & 1 \\ 
%\hline 
%5 & 454 & 0 & -1 & 1 & 0 \\ 
%\hline 
%2 & 445 & -1 & 1 & 2 & 1 \\ 
%\hline 
%3 & 364 & 1 & 0 & 1 & 0 \\ 
%\hline 
%7 & 361 & -1 & 0 & 1 & 0 \\ 
%\hline 
%4 & 356 & -1 & -1 & 2 & 1 \\ 
%\hline 
%0 & 321 & 1 & 1 & 2 & 1 \\ 
%\hline 
%\end{tabular} }
%
%\caption{Độ quan trọng của véc tơ $\mathcal{M}_{Lut}$ trong trích xuất MA với hai ảnh khác nhau (số thứ tự trong $\mathcal{M}_{Lut}$ gốc, số lần sử dụng, tọa độ x, tọa độ y, giá trị véc tơ, số thứ tự véc tơ $\mathcal{M}_{Lut}^g$ tương ứng).}
%\label{doquantrongvecto}
%\end{table}

%\begin{tabular}{|c|c|cc|c|c|}
%\hline 
%5 & 166 & 0 & -1 & 1 & 0 \\ 
%\hline 
%1 & 163 & 0 & 1 & 1 & 0 \\ 
%\hline 
%6 & 130 & 1 & -1 & 2 & 1 \\ 
%\hline 
%2 & 123 & -1 & 1 & 2 & 1 \\ 
%\hline 
%7 & 117 & -1 & 0 & 1 & 0 \\ 
%\hline 
%3 & 109 & 1 & 0 & 1 & 0 \\ 
%\hline 
%0 & 75 & 1 & 1 & 2 & 1 \\ 
%\hline 
%4 & 68 & -1 & -1 & 2 & 1 \\ 
%\hline 
%\end{tabular} 
%
%\begin{tabular}{|c|c|cc|c|c|}
%\hline 
%1 & 473 & 0 & 1 & 1 & 0 \\ 
%\hline 
%6 & 472 & 1 & -1 & 2 & 1 \\ 
%\hline 
%5 & 454 & 0 & -1 & 1 & 0 \\ 
%\hline 
%2 & 445 & -1 & 1 & 2 & 1 \\ 
%\hline 
%3 & 364 & 1 & 0 & 1 & 0 \\ 
%\hline 
%7 & 361 & -1 & 0 & 1 & 0 \\ 
%\hline 
%4 & 356 & -1 & -1 & 2 & 1 \\ 
%\hline 
%0 & 321 & 1 & 1 & 2 & 1 \\ 
%\hline 
%\end{tabular} 

Nếu ta áp dụng tính toán với số lượng ảnh đủ lớn, tính chất này cho phép xác định những véc tơ quan trọng nhất của $\mathcal{M}_{Lut}$, do đó giảm thời gian trích xuất MA.

Thực nghiệm khác trên vật thể 2D với ảnh là một hình vuông cạnh 256 (chứa 65536 điểm ảnh), vật thể chứa 16096 điểm ảnh. Thời gian tính toán không tối ưu là 0.19 giây. Sau đó, chúng tôi lưu các véc tơ $\mathcal{M}_{Lut}$ và sắp xếp theo độ quan trọng. Khi áp dụng $\mathcal{M}_{Lut}$ đã sắp xếp vào cùng một ảnh ban đầu, thời gian tính toán giảm còn 0.09 giây.

Tương tự, khi kiểm tra với một vật thể 3D. Ảnh là một hình hộp cạnh 150 (chứa 3375000 điểm ảnh), vật thể chứa 233412 điểm ảnh. Thời gian tính toán giảm từ 121 giây còn 29.39 giây.

\subsection{Mối quan hệ giữa trục xương và biên vật thể}

Chúng tôi chọn ví dụ (Hình \ref{fig:goniol1}) là một vật thể 2D (a). Ảnh là một hình vuông cạnh 256 (chứa 65536 điểm ảnh). chúng tôi tính ảnh khoảng cách DT (b) và trục xương (c) với bình phương khoảng cách Euclide $d_E^2$.


Hình \ref{fig:goniol2} biểu diễn mối quan hệ giữa trục xương và biên vật thể. Với một ảnh, ta có những phần khác nhau với màu tương ứng như sau. Màu vàng biểu diễn biên vật thể, màu đỏ biểu diễn trục xương, màu xanh dương biểu diễn phần còn lại của vật thể (trừ biên và trục xương), màu tím biểu diễn điểm biên bị ngăn bởi điểm trục xương màu xanh da trời, màu xanh da trời biểu diễn điểm trục xương ngăn điểm biên màu tím, màu cam biểu diễn các điểm trung gian tạo nên con đường giữa điểm xanh da trời và điểm tím.
%\begin{itemize}
%\item Vàng: biên vật thể;
%\item Đỏ: trục xương;
%\item Xanh dương: phần còn lại của vật thể (trừ biên và trục xương);
%\item Tím: điểm biên bị ngăn bởi điểm trục xương màu xanh da trời;
%\item Xanh da trời: điểm trục xương ngăn điểm biên màu tím;
%\item Cam: các điểm trung tâm tạo nên con đường giữa điểm xanh da trời và điểm tím.
%\end{itemize}

%\begin{tabular}{|l|l|}
%\hline 
%Vàng & Biên vật thể \\ 
%\hline 
%Đỏ & Trục xương \\ 
%\hline 
%Xanh dương & \multicolumn{1}{m{4cm}|}{Phần còn lại của vật thể (trừ biên và trục xương)} \\ 
%\hline 
%Tím & \multicolumn{1}{m{4cm}|}{Điểm biên bị ngăn bởi điểm trục xương màu xanh da trời} \\ 
%\hline 
%Xanh da trời & \multicolumn{1}{m{4cm}|}{Điểm trục xương ngăn điểm biên màu tím} \\ 
%\hline 
%Cam & \multicolumn{1}{m{4cm}|}{Các điểm trung tâm tạo nên con đường giữa điểm xanh da trời và điểm tím} \\ 
%\hline 
%\end{tabular} 

\begin{figure}
  \centering           
  \subfloat[]{\label{fig:bordtomagoniol1}\includegraphics[width=0.25\textwidth]{figs/bordtomagoniol1}}
  \hspace*{1.9em}
  \subfloat[]{\label{fig:bordtomagoniol2}\includegraphics[width=0.12\textwidth]{figs/bordtomagoniol2}}
  
  \subfloat[]{\label{fig:matobordgoniol1}\includegraphics[width=0.25\textwidth]{figs/matobordgoniol1}}
  \hspace*{1.9em}
  \subfloat[]{\label{fig:matobordgoniol2}\includegraphics[width=0.12\textwidth]{figs/matobordgoniol2}}
  \caption{Mối quan hệ giữa trục xương và biên vật thể.}
  \label{fig:goniol2}
\end{figure}

%\vspace{0.5em}
Ở (a) và (b), khi người dùng chọn một điểm biên, kết quả là tập điểm của trục xương ngăn điểm này trở thành một phần của trục xương. Ở (c) và (d), người dùng chọn một điểm trục xương, kết quả là tập điểm biên bị ngăn bởi điểm này trở thành một phần của trục xương.

\subsection{Đánh giá kết quả}
Phương pháp xác định ảnh hưởng giữa trục xương và biên vật thể được đề xuất cho kết quả chính xác. Tuy nhiên khi thực nghiệm, phương pháp chỉ triển khai tốt nếu dữ liệu đầu vào nhỏ: ảnh 2D hình vuông có cạnh nhỏ hơn 500 điểm ảnh, ảnh 3D hình hộp có cạnh nhỏ hơn 300 điểm ảnh. Ngoài ra, vì độ phức tạp của thuật toán lớn, chúng tôi giới hạn số con đường nối mỗi cặp \textit{điểm trục xương - điểm biên} là một.

\section{Kết luận}
Trong bài báo này, chúng tôi đã sử dụng thuật toán được trình bày trong \cite{Saito19941551} để tính chuyển đổi khoảng cách Euclide. Tiếp theo, chúng tôi tính trục xương từ ảnh chuyển đổi khoảng cách của vật thể dựa vào \cite{remy2001normes}. Dựa vào bảng tìm kiếm $Lut$ và vùng kiểm tra lân cận $\mathcal{M}_{Lut}$, chúng tôi đề xuất một phương pháp cho phép xóa những điểm nhiễu của trục xương, dựa trên thuật toán tìm kiếm cây nhị phân theo chiều rộng. Phương pháp này cho phép xác định độ quan trọng của một điểm nằm trên trục xương và giải quyết vấn đề đơn giản hóa trục xương. Thực nghiệm được thể hiện thông qua việc tìm số lần sử dụng của một véc tơ trong mặt nạ khi trích xuất trục xương, và mối quan hệ giữa trục xương và biên vật thể. Đây là bước khởi đầu và có thể phát triển trong việc xác định các yếu tố của đường cong ở biên vật thể.

% conference papers do not normally have an appendix


% use section* for acknowledgement
\section*{Lời cảm ơn}


Tôi xin gửi lời biết ơn sâu sắc đến Prof. Eric Remy đã gợi ý và chỉ dẫn để thực hiện hướng nghiên cứu này.


% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
\bibliography{IEEEabrv,references}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
%\begin{thebibliography}{1}
%
%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
%
%\end{thebibliography}




% that's all folks
\end{document}


